package tree;

import java.util.TreeMap;

/**
 * Trie：字典树、前缀树
 * pan panda
 */
public class Trie {

    private class Node{

        public boolean isWord;
        public TreeMap < Character , Node > next;

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap<>();
        }

        public Node(){
            this(false);
        }
    }

    private int size;
    private Node root;

    public Trie(){
        root = new Node();
        size = 0;
    }

    public int getSize(){
        return size;
    }

    // 添加单词
    public void add(String word){

        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            //将c作为一个节点插入到trie中，先检查cur的next节点映射中，是否已有指向c的引用
            if(cur.next.get(c) == null){
                //c没有存在于cur的映射中
                cur.next.put(c,new Node());
            }
            cur = cur.next.get(c);
        }


        //判断单词以前是否存在，不存在才创建
        if(!cur.isWord){
            cur.isWord = true;
            size++;
        }

    }

    // 查看 Trie中是否包含有word
    public boolean contains(String word){

        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if( cur.next.get(c) == null ){
                return false;
            }

            cur = cur.next.get(c);
        }

        return cur.isWord;
    }

    // Trie 前缀搜索,从Trie中查找，是否有以prefix中为前缀的单词
    public boolean isPrefix(String prefix){

        Node cur = root;
        for (int i = 0; i < prefix.length() ; i++) {
            char c = prefix.charAt(i);
            if( cur.next.get(c) == null ){
                return false;
            }
            //下一个节点
            cur = cur.next.get(c);
        }
        return true;
    }

    /**
     * Trie中的前缀搜索
     * @param node
     * @param prefix
     * @param index
     * @return
     */
    public boolean isPrefix(Node node , String prefix, int index){



        if( index == prefix.length()){
            return true;
        }

        char c = prefix.charAt(index);
        if(node.next.get(c) == null){
            return false;
        }
        return isPrefix(node.next.get(c) , prefix , index + 1);

    }

    private void removeWord(Node node , String word , int index){
        if( index == word.length() ){
            if(node.isWord == true){
                node.isWord = false;
            }
            return;
        }

        char c = word.charAt(index);
        removeWord(node.next.get(c) , word ,index + 1);

        //后序遍历
        if(node.next.get(c) == null){
            //该node可以被删除
            node.next = null;
        }

    }


    //  向以node为根的Trie中添加word[index...end), 递归算法
//    private void add(Node node , String word , int index){
//
//        if( index == word.length()){
//            //递归完毕，需要退出
//            if(node.isWord == false){
//                node.isWord = true;
//                size++;
//            }
//            return;
//        }
//
//        char c = word.charAt(index);
//        if( node.next.get(c) == null ){
//            node.next.put(c , new Node());
//        }
//
//        add(node.next.get(c), word ,index+1);
//    }

//    private void add(Node node , String word , int index){
//        if( index == word.length()){
//            if( node.isWord == false ){
//                node.isWord = true;
//                size++;
//            }
//            return;
//        }
//
//        char c = word.charAt(index);
//        if( node.next.get(c) == null ){
//            //添加节点
//            node.next.put(c , new Node());
//        }
//
//        add(node.next.get(c) , word , index + 1);
//    }

    // 查看Trie中是否包含某一单词，递归算法
//    private boolean contains(Node node , String word , int index){
//        if( index == word.length() ){
//            return node.isWord;
//        }
//
//        char c = word.charAt(index);
//        if(node.next.get(c) == null){
//            return false;
//        }
//        return contains(node.next.get(c) , word , index + 1);
//    }






}
